/*
 * Pascal’s Triangle using a Circular Queue
 * gcc pascal_cq.c -o pascal_cq
 */
#include <stdio.h>
#include <stdlib.h>

#define MAXQ 1024          /* big enough for any reasonable height */

typedef struct {
    int data[MAXQ];
    int front, rear;
} CQueue;

/* ---------- basic circular-queue operations ---------- */
void init(CQueue *q) {
    q->front = 0;
    q->rear  = 0;
}

int isEmpty(CQueue *q) {
    return q->front == q->rear;
}

int isFull(CQueue *q) {
    return (q->rear + 1) % MAXQ == q->front;
}

void enqueue(CQueue *q, int val) {
    if (isFull(q)) {
        fprintf(stderr, "Queue overflow\n");
        exit(EXIT_FAILURE);
    }
    q->data[q->rear] = val;
    q->rear = (q->rear + 1) % MAXQ;
}

int dequeue(CQueue *q) {
    if (isEmpty(q)) {
        fprintf(stderr, "Queue underflow\n");
        exit(EXIT_FAILURE);
    }
    int val = q->data[q->front];
    q->front = (q->front + 1) % MAXQ;
    return val;
}

int main(void) {
    int n;
    printf("请输入行数: ");
    if (scanf("%d", &n) != 1 || n < 0) {
        puts("Invalid input");
        return 0;
    }

    CQueue q;
    init(&q);


     /* 初始化：第一行包只有一个元素 1 */
    enqueue(&q, 1);

    for (int row = 0; row < n; ++row) {
        /* 输出空格以实现金字塔效果 */
        for (int sp = 0; sp < n - row - 1; ++sp)
            printf("  ");

        /* 从队列里输出的同时构建下一行的新元素 */
        /* 新元素左前方的元素值 */
        int prev = 0;
        /* 当前行里的元素个数 */
        int count = row + 1;

 for (int i = 0; i < count; ++i) {
            int curr = dequeue(&q);
            printf("%4d", curr);

            /* 基于滚动的prev和curr构建下一行的元素的值 */
            enqueue(&q, prev + curr);
            prev = curr;
        }
        /* 上面for循环构建了count个值，二下一行其实有count+1个值（最后一个元素值为1，因此： */
        enqueue(&q, 1);

        putchar('\n');
    }
    return 0;
}


/* ---------- Pascal triangle driver ---------- */
int main2(void) {
    int n;
    printf("Enter number of rows: ");
    if (scanf("%d", &n) != 1 || n < 0) {
        puts("Invalid input");
        return 0;
    }

    CQueue q;
    init(&q);

    /* first row (row 0) */
    enqueue(&q, 1);

    for (int row = 0; row < n; ++row) {
        /* indent for pretty triangle */
        for (int sp = 0; sp < n - row - 1; ++sp)
            printf("  ");

        /* print and build next row in the same queue */
        int prev = 0;                 /* left boundary for each new row */
        int count = row + 1;          /* number of elements in current row */

        for (int i = 0; i < count; ++i) {
            int curr = dequeue(&q);
            printf("%4d", curr);

            /* store the next-row value back into the queue */
            enqueue(&q, prev + curr);
            prev = curr;
        }
        /* right boundary of the row */
        enqueue(&q, 1);

        putchar('\n');
    }
    return 0;
}
